High compression gains for video sequences can be achieved by removing temporal redundancies between images (frames). For example, to encode an image, a temporal prediction of the image to be encoded is generated based on previously encoded images. The temporal prediction is compared with the actual image to determine the prediction error, and the prediction error is encoded. The prediction can be made using block-based motion estimation and compensation methods, which are widely used (e.g., MPEG standards).
Motion compensation and estimation methods are used to find a reference block in one or more reference images to predict the location of a corresponding target block in the target image, so that only the prediction residual of the target block needs to be coded, which is typically the prediction error and motion vector. These methods perform block matching to identify a reference block of pixels in the reference image that is most similar to a corresponding target block in the target image.
FIG. 1 is a diagrammatic view of an illustrative motion vector, reference block, and target block. Target image 120 is to be encoded using information from reference image 110. Reference block 115 is identified as the block in reference image 110 that most closely matches a target block 125 in target image 120. After the reference block is identified, motion vector 130 (shown as an arrow for illustrative purposes only) is generated to identify the position of target block 125 relative to the position of reference block 115. Motion vector 130 has two elements that represent the relationship between reference block 115 and target block 125: a horizontal displacement and a vertical displacement. For example, reference block 115, which is an illustrative 3×3 group of pixels, is at location (i′, j′), and target block 125 is at location (i, j). The distance between the two blocks is the motion vector (i′-i, j′-j).
The values of the motion vector are used in video compression, along with the reference block, to generate a prediction value for the target block. For example, if a target block S is associated with a motion vector and corresponding reference block, then each pixel in the target block is predicted as:{circumflex over (v)}(x,y,t)=v(x+mx,y+my,k), for all v(x,y,t)εS,  (1)where {circumflex over (v)}(x,y,t) is the predicted pixel value in the target block, located at pixel coordinate (x,y), t is the time index of the target image, v(x+mv,y+my,k) is the pixel value in the reference block (indexed by k), and [mx,my] is the motion vector to represent the offset of the pixel in the reference block relative to the location of the pixel to be predicted in the target block.
To predict an entire target image, a typical method divides the target image into several non-overlapping target blocks. Then, motion estimation is performed for each target block to determine its corresponding reference block and motion vector. In general, the target and reference blocks created by the motion estimation process have the same shape and contain the same amount of pixels, so that there is a one to one mapping between each target and reference pixel.
One example of a method for creating target blocks can be found in MPEG, which divides the target image into target blocks having a fixed amount of pixels (i.e., 16×16 pixels). More advanced video codecs allow the shapes and sizes of the target blocks to vary (with some limitations). For example, MPEG/AVC allows the block size to vary from 4×4 up to 16×16 pixels.
In general, traditional block creation methods work well when creating a regular pattern of fixed-size target and reference blocks. Motion estimation methods, on the other hand, have better prediction performance when the target and reference blocks have variable shapes and sizes. However, creating an efficient pattern of target blocks that vary in size and shape is beyond the capabilities of traditional block creation methods. There is a need for a method that efficiently creates variable shaped blocks in the target image to be used by a motion estimation method.